{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Removing Stars From a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeStars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从字符串中移除星号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个包含若干星号 <code>*</code> 的字符串 <code>s</code> 。</p>\n",
    "\n",
    "<p>在一步操作中，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选中 <code>s</code> 中的一个星号。</li>\n",
    "\t<li>移除星号 <strong>左侧</strong> 最近的那个 <strong>非星号</strong> 字符，并移除该星号自身。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回移除 <strong>所有</strong> 星号之后的字符串<strong>。</strong></p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>生成的输入保证总是可以执行题面中描述的操作。</li>\n",
    "\t<li>可以证明结果字符串是唯一的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leet**cod*e\"\n",
    "<strong>输出：</strong>\"lecoe\"\n",
    "<strong>解释：</strong>从左到右执行移除操作：\n",
    "- 距离第 1 个星号最近的字符是 \"lee<em><strong>t</strong></em>**cod*e\" 中的 't' ，s 变为 \"lee*cod*e\" 。\n",
    "- 距离第 2 个星号最近的字符是 \"le<em><strong>e</strong></em>*cod*e\" 中的 'e' ，s 变为 \"lecod*e\" 。\n",
    "- 距离第 3 个星号最近的字符是 \"leco<em><strong>d</strong></em>*e\" 中的 'd' ，s 变为 \"lecoe\" 。\n",
    "不存在其他星号，返回 \"lecoe\" 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"erase*****\"\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>整个字符串都会被移除，所以返回空字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母和星号 <code>*</code> 组成</li>\n",
    "\t<li><code>s</code> 可以执行上述操作</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [removing-stars-from-a-string](https://leetcode.cn/problems/removing-stars-from-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [removing-stars-from-a-string](https://leetcode.cn/problems/removing-stars-from-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leet**cod*e\"', '\"erase*****\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        curr_pt = 0\n",
    "\n",
    "        stack_processed = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                stack_processed.pop()\n",
    "            else:\n",
    "                stack_processed.append(s[i])\n",
    "        \n",
    "        return ''.join(stack_processed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s):\n",
    "        ans = ''\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            p = len(s) - 1 - i\n",
    "            if cnt == 0:\n",
    "                if s[p] == '*':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    ans = s[p] + ans\n",
    "            else:\n",
    "                if s[p] == '*':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "\n",
    "        data = ''\n",
    "\n",
    "        for char in s:\n",
    "            if char == '*' and len(data) != 0:\n",
    "                data = data[:-1]\n",
    "            elif char != '*':\n",
    "                data += char\n",
    "        \n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        result = \"\"\n",
    "        for i in s:\n",
    "            if i == \"*\":\n",
    "                result = result[:-1]\n",
    "            else:\n",
    "                result += i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        res = []\n",
    "        for w in s:\n",
    "            if w != '*':\n",
    "                res.append(w)\n",
    "            else:\n",
    "                res.pop()\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        del_index=[(0,0)]\n",
    "        start,end=None,None\n",
    "        for i,one in enumerate(s):\n",
    "            if one=='*':\n",
    "                if start==None:start=i\n",
    "                start-=1\n",
    "                if len(del_index)!=1 and start==del_index[-1][1]:\n",
    "                    start,_=del_index.pop()\n",
    "                end=i+1\n",
    "            elif start!=None:\n",
    "                del_index.append((start,end))\n",
    "                start,end=None,None\n",
    "        if start!=None:del_index.append((start,end))\n",
    "        r=''\n",
    "        for i in range(len(del_index)-1):\n",
    "            r+=s[del_index[i][1]:del_index[i+1][0]]\n",
    "        r+=s[del_index[-1][1]:]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        k = 0\n",
    "        ss = \"\"\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            if s[i] == '*':\n",
    "                k += 1\n",
    "            else:\n",
    "                if k == 0:\n",
    "                    ss = s[i]+ss\n",
    "                else:\n",
    "                    k -= 1\n",
    "        return ss\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            if s[i] == \"*\":\n",
    "                s = s[:i-1] + s[i+1:]\n",
    "                i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        candidates = []\n",
    "        for c in s:\n",
    "            if c == '*':\n",
    "                candidates.pop()\n",
    "            else:\n",
    "                candidates.append(c)\n",
    "        return ''.join(candidates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        st=[]\n",
    "        for c in s:\n",
    "            if c=='*':\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if c == '*': st.pop() # 如果当前字符是*的话，删除stack里面最后一个\n",
    "            else: st.append(c) # 如果不是的话，加到stack里面\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        for char in s:\n",
    "            if char == '*':\n",
    "                try: stack.pop()\n",
    "                except IndexError: pass                    \n",
    "            else:\n",
    "                stack.append(char)\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStars(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        stack = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "        return ''.join(stack)\n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
